from typing import List


class Solution:
    def __init__(self):
        self.result = []

    def generateParenthesis(self, n: int) -> List[str]:
        self._generate(left=0, right=0, n=n, param="")
        return self.result

    def _generate(self, left: int, right: int, n: int, param: str):
        # terminator
        if left == n and right == n:
            self.result.append(param)

        # process and drill down
        if left < n:
            self._generate(left + 1, right, n, param + "(")
        if right < left:
            self._generate(left, right + 1, n, param + ")")

        # reverse states


if __name__ == '__main__':
    s = Solution().generateParenthesis(n=3)
    print(s)
